package com.longge;

public class CountNodes {

    int h = 0,moreCount = 0;
    boolean flag = false;
    public int countNodes(TreeNode root) {
        int k = getDep(root);
        int fullCount = (int) Math.pow(2, k) - 1;
        return fullCount - getMoreCount(root,k);
    }

    private int getMoreCount(TreeNode root,Integer k) {
        if (flag) return moreCount;
        if (root==null&&h!=k) {
            moreCount++;
            return moreCount;
        }else if (root==null){
           flag = true;
           return moreCount;
        }
        h++;
        getMoreCount(root.right,k);
        getMoreCount(root.left,k);
        h--;
        return moreCount;
    }

    private int getDep(TreeNode root) {
        if (root == null) return 0;
        int dep = getDep(root.left);
        return dep + 1;
    }


}
